package com.leecode.xiehf.page_05;

import com.leecode.Printer;

/**
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。
 * <p>
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/house-robber-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0213 extends Printer {

    public static void main(String[] args) {
        Solution_0213 solution = new Solution_0213();
        // ["app"],["apple"],["beer"],["add"],["jam"],["rental"],["apps"],["app"],["ad"],["applepie"],["rest"],["jan"],["rent"],["beer"],["jam"],
        // ["apps"],["app"],["ad"],["applepie"],["rest"],["jan"],["rent"],["beer"],["jam"]
//        int[] ints = {1, 1, 3, 6, 7, 10, 7, 1, 8, 5, 9, 1, 4, 4, 3};
//        int[] ints = {2, 1, 2, 6, 1, 8, 10, 10};
        int[] ints = {0, 0};
//
        int rob = solution.rob(ints);
        print(rob);
    }

    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        return Math.max(getMax(nums, 1, length), getMax(nums, 0, length - 1));
    }

    private int getMax(int[] nums, int start, int end) {
        int[] dp = new int[nums.length];
        for (int i = start; i < end; i++) {
            if (i >= 2) {
                if (i >= 3) {

                    // 2 1 1 3
                    if (dp[i - 2] >= dp[i - 3]) {
                        dp[i] = dp[i - 2] + nums[i];
                    } else {
                        dp[i] = dp[i - 3] + nums[i];
                    }

                } else {
                    dp[i] = dp[i - 2] + nums[i];
                }
            } else {
                dp[i] = nums[i];
            }
        }
        if (end - start > 1) {
            return Math.max(dp[end - 1], dp[end - 2]);
        } else if (end - start == 1) {
            return Math.max(dp[end - 1], dp[0]);
        }
        return dp[end - 1];
    }
}
